package hp_approximation;

/**
 * @author Marcus Schroeder & Paula Tataru
 * 
 * implements the U-Fold algorihtm for the 2D HP model for protein folding
 *
 * given a string S of h and p, align S with S reversed
 * scoring funcion:
 * a match between 2 h's scores 1, the other matches score 0
 * a gap scores 0
 * all gaps blocks must have even length
 * between two gap blocks in the same string there must be at least 2 matched characters
 * objective: maximize
 * find k so that the entry (k, n-k) has maximum value in the cost matrix
 *
 * how do I verify this:
 * between two gap blocks in the same string there must be at least 2 matched characters ?
 * I have two other matrices, gap, gapR
 * that tell me how many consecutive matches I had after last gap block
 * gap keeps track for S and gapR for the reversed string
 * when I want to add gaps, I have to check the matrices
 * value: 0 if the last thing I have is a gap, x for x matched characters
 *
 * h - doesn't like water; p - likes water
 */

public class UFold {

    String S, op, fold;
    String[] Sa;
    int n, k;
    int[][] c;

    /**
     * default constructor
     */
    UFold(String x) {
        S = x;
        op = new String();
        fold = new String();
        Sa = new String[2];
        Sa[0] = new String();
        Sa[1] = new String();
        n = S.length();
        k = 0;
        c = new int[n+1][n+1];
    }

    /**
     * returns the score of two matched characters
     */
    int score(char a, char b) {
        if(a=='h' && b=='h')
            return 1;
        return 0;
    }

    /**
     * computes the cost matrix
     */
    void cost_matrix() {
        int[][] gap, gapR;
        gap = new int[n+1][n+1];
        gapR = new int[n+1][n+1];
        int max = -1;
        int i,j;
        for(i=0; i<=n; i++) {
            for(j=0; j<=n; j++) {
                int v1, v2, v3, v4;
                v1 = v2 = v3 = v4 = -5000;
                if(i>0&&j>0)
                    v1 = c[i-1][j-1] + score(S.charAt(i-1),S.charAt(n-j));
                // between two gap blocks in the same string there must be at least 2 matched characters
                // whenever I have gap, I add 2 - because the gap blocks are even
                if(i>1&&j>=0&&gapR[i-2][j]!=1)
                    v2 = c[i-2][j];
                if(i>=0&&j>1&&gap[i][j-2]!=1)
                    v3 = c[i][j-2];
                if((i==0&&j==0)||(i==1&&j==0)||(i==0&&j==1))
                    v4 = 0;
                c[i][j] = java.lang.Math.max(java.lang.Math.max(v1, v2),java.lang.Math.max(v3, v4));
                if(c[i][j]==v1) {
                    gap[i][j] = gap[i-1][j-1]+1;
                    gapR[i][j] = gapR[i-1][j-1];
                }
                else
                    if(c[i][j]==v2) {
                        gapR[i][j] = 0;
                        gap[i][j] = gap[i-2][j];
                    }
                    else
                        if(c[i][j]==v3) {
                            gapR[i][j] = gapR[i][j-2];
                            gap[i][j] = 0;
                        }
                if(j == n-i)
                    if(max<c[i][j]) {
                        max = c[i][j];
                        k = i;
                    }
            }
        }
        // now I compute the operations needed for the alignment
        i = k; j = n-k;
        while((i!=0)||(j!=0)){
            if(i == 0) {
                j--;
                op = op.concat("I");
            }
            else
                if(j == 0) {
                    i--;
                    op = op.concat("D");
                }
                else {
                int v1, v2, v3;
                v2 = v3 = 0;
                v1 = c[i-1][j-1] + score(S.charAt(i-1),S.charAt(n-j));
                if(i>1&&gapR[i-2][j]!=1)
                    v2 = c[i-2][j];
                if(j>1&&gap[i][j-2]!=1)
                    v3 = c[i][j-2];
                int m = java.lang.Math.max(java.lang.Math.max(v1,v2),v3);
                if(v1==m) {
                    op = op.concat("M");
                    i--;
                    j--;
                }
                else
                    if(v2==m) {
                        op = op.concat("DD");
                        i-=2;
                    }
                    else
                        if(v3==m) {
                            op = op.concat("II");
                            j-=2;
                        }
                }
        }
    }

    /**
     * print the optimal alignement
     */
    void build_alignment() {
        //build the first part of S
        int i, j;
        j = 0;
        for(i=op.length()-1; i>=0; i--) {
            if((op.charAt(i)=='M')||(op.charAt(i)=='D')) {
                Sa[0] = Sa[0].concat(Character.toString(S.charAt(j)));
                j++;
            }
            if(op.charAt(i)=='I')
                Sa[0] = Sa[0].concat("-");
        }
        //print the second part of S - reversed
        j = n-1;
        for(i=op.length()-1; i>=0; i--) {
            if((op.charAt(i)=='M')||(op.charAt(i)=='I')) {
                Sa[1] = Sa[1].concat(Character.toString(S.charAt(j)));
                j--;
            }
            if(op.charAt(i)=='D')
                Sa[1] = Sa[1].concat("-");
        }

        System.out.println("Input: "+S);
        System.out.println("Cost: "+c[k][n-k]);
        System.out.println(Sa[0]);
        System.out.println(Sa[1]);
        System.out.println();
    }

    /**
     * return the alignment - S1 and S2
     */
    public String[] get_alignment() {
        return Sa;
    }

    /**
     * build the sequence that gives the fold using absolute format
     * n = North
     * s = South
     * e = East
     * w = West
     */
    public String build_fold() {

        this.cost_matrix();
        this.build_alignment();

        int s = Sa[0].length();
        int end = s;
        int i;

        // build the sequence for Sa[0]
        // I check if I have a gap block at the end of Sa[0]
        i = s-1;
        if(Sa[0].charAt(i)=='-') {
            int l = i;
            while(Sa[0].charAt(i)=='-')
                i--;
            l = l-i;
            end = i;
        }
        i = 1;
        // I check if I have a gap block at the begining of Sa[1]
        if(Sa[1].charAt(i)=='-') {
            int l = 0;
            while(Sa[1].charAt(i)=='-')
                i++;
            l = i - l;
            for(int j=0; j<(l/2)-1; j++)
                fold = fold.concat("n");
            fold = fold.concat("e");
            for(int j=0; j<(l/2); j++)
                fold = fold.concat("s");
            i++;
        }
        // I check if I have a gap block at the begining of Sa[0]
        if(Sa[0].charAt(i)=='-') {
            while(Sa[0].charAt(i)=='-')
                i++;
            i++;
        }
        // now treat the rest of the sequence
        while(i<end) {
            if(Sa[1].charAt(i)!='-') {
                if(i<end&&Sa[1].charAt(i)!='-'&&Sa[0].charAt(i)!='-')
                    fold = fold.concat("e");
                i++;
                if(i<end&&Sa[0].charAt(i)=='-')
                    while(i<s&&Sa[0].charAt(i)=='-')
                        i++;
                else
                    if(i==s)
                    // I'm done with Sa[0], I go to Sa[1]
                    fold = fold.concat("s");
            }
            else {
                // I have a gap block in Sa[1]
                int l = i;
                while(i<end&&(Sa[1].charAt(i)=='-'))
                    i++;
                l = i-l;
                // I first check if it's at the end of Sa[1]
                if(i==s) {
                    for(int j=0; j<(l/2); j++)
                        fold = fold.concat("e");
                    fold = fold.concat("s");
                    for(int j=0; j<(l/2); j++)
                        fold = fold.concat("w");
                    // I'm done with Sa[0] and I went to Sa[1]
                }
                else {
                    for(int j=0; j<(l/2); j++)
                        fold = fold.concat("n");
                    fold = fold.concat("e");
                    for(int j=0; j<(l/2); j++)
                        fold = fold.concat("s");
                    // if I have gaps in Sa[0], I skip them
                    if(Sa[0].charAt(i)=='-') {
                        while(Sa[0].charAt(i)=='-')
                            i++;
                    }
                    i++;
                }
            }
        }


        // build the sequence for Sa[1]
        i = s-1;
        // I first deal with the gap block at the end of Sa[0] - if I have one
        if(end!=s) {
            fold = fold.concat("e");
            int l = i;
            while(Sa[0].charAt(i)=='-')
                i--;
            l = l-i;
            for(int j=0; j<(l/2); j++)
                fold = fold.concat("e");
            fold = fold.concat("s");
            for(int j=0; j<(l/2); j++)
                fold = fold.concat("w");
        }
        // I deal with the gap block at the end of Sa[1] - if I have one
        else
            while(Sa[1].charAt(i)=='-')
                i--;

        // now I can build the rest of Sa[1]
        while(i>1) {
            if(Sa[0].charAt(i-1)!='-') {
                //System.out.println(fold+" I will add a w "+i);
                fold = fold.concat("w");
                i--;
                //System.out.println("I decreased i to "+i);
                //System.out.println("I check for gaps in Sa[1] "+i+" "+Sa[1].charAt(i));
                if(i>0&&Sa[1].charAt(i-1)=='-')
                    while(i>0&&Sa[1].charAt(i-1)=='-')
                        i--;
                //System.out.println("Did I have any gaps? "+i);
            }
            else {
                // I have a gap block in Sa[0]
                int l = i;
                i--;
                while(i>0&&(Sa[0].charAt(i)=='-'))
                    i--;
                l = l-i;
                for(int j=0; j<(l/2); j++)
                    fold = fold.concat("s");
                fold = fold.concat("w");
                // I check if the gap block is at the begining or I have a gap block in Sa[1]
                if(i==0||Sa[1].charAt(i)=='-') {
                    int j = i;
                    while(j>0&&Sa[1].charAt(j)=='-')
                        j--;
                    if(j==0||j==i)
                        for(j=0; j<(l/2)-1; j++)
                            fold = fold.concat("n");
                    else
                        for(j=0; j<(l/2); j++)
                            fold = fold.concat("n");
                    if(j!=i)
                        i = j;
                }
                else
                    for(int j=0; j<(l/2); j++)
                        fold = fold.concat("n");
            }
        }
        if(i==1&&Sa[1].charAt(i)!='-')
            fold = fold.concat("w");

        return fold;
    }

}
